package problems

import (
	"fmt"
	"math"
	"strconv"
	"strings"
)

// IsHappy
// 202
// https://leetcode-cn.com/problems/happy-number/
func IsHappy(n int) bool {
	if n == 0 {
		return false
	}
	res := 0
	for n > 0 {
		n, res = n/10, res+(n%10)*(n%10)
	}

	if res == 1 {
		return true
	}
	if res == 4 {
		return false
	}
	return IsHappy(res)
}

// 203
// https://leetcode-cn.com/problems/remove-linked-list-elements/
func RemoveElements(head *ListNode, val int) *ListNode {
	var current, last *ListNode = head, nil
	for current != nil {
		if current.Val == val {
			if last == nil {
				head = current.Next
			} else {
				last.Next = current.Next
			}
		} else {
			last = current
		}
		current = current.Next
	}
	return head
}

// 204
// https://leetcode-cn.com/problems/count-primes/
func CountPrimes(n int) int {
	var count = 0
	var stack = make([]bool, n)
	for i := 2; i < n; i++ {
		if !stack[i] {
			count++
			for j := i * 2; j < n; j += i {
				stack[j] = true
			}
		}
	}
	return count
}

// 205
// https://leetcode-cn.com/problems/isomorphic-strings/
func IsIsomorphic(s string, t string) bool {
	var sMap, tMap = make(map[rune]rune), make(map[rune]rune)
	for k, v := range s {
		var tv = rune(t[k])
		if _, oks := sMap[v]; oks {
			if sMap[v] != tv {
				return false
			}
		} else {
			if _, okt := tMap[tv]; okt {
				return false
			}
			sMap[v] = tv
			tMap[tv] = v
		}
	}
	return true
}

// ReverseList
// 206
// https://leetcode-cn.com/problems/reverse-linked-list/
func ReverseList(head *ListNode) *ListNode {
	var prev *ListNode
	for head != nil {
		head.Next, head, prev = prev, head.Next, head
	}

	return prev
}

// 208
// https://leetcode-cn.com/problems/implement-trie-prefix-tree/
type Trie struct {
	Children [26]*Trie
	self     bool
}

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{}
}

/** Inserts a word into the trie. */
func (t *Trie) Insert(word string) {
	if len(word) == 0 {
		return
	}
	node := t
	for _, v := range word {
		key := v - 'a'
		if node.Children[key] == nil {
			node.Children[key] = &Trie{}
		}
		node = node.Children[key]
	}
	node.self = true
}

/** Returns if the word is in the trie. */
func (t *Trie) Search(word string) bool {
	if len(word) == 0 {
		return true
	}
	node := t
	for _, v := range word {
		key := v - 'a'
		if node.Children[key] == nil {
			return false
		}
		node = node.Children[key]
	}
	return node.self
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (t *Trie) StartsWith(prefix string) bool {
	if len(prefix) == 0 {
		return true
	}
	node := t
	for _, v := range prefix {
		key := v - 'a'
		if node.Children[key] == nil {
			return false
		}
		node = node.Children[key]
	}
	return true
}

// 213
// https://leetcode-cn.com/problems/house-robber-ii/
func Rob3(nums []int) int {
	dp := func(nums []int) int {
		arr, dp := append([]int{0, 0}, nums...), []int{0, 0, 0}
		for i := 2; i < len(arr); i++ {
			dp = append(dp, arr[i]+dp[i-1])
			if dp[i+1] < dp[i] {
				dp[i+1] = dp[i]
			}
		}
		return dp[len(nums)+2]
	}
	if len(nums) <= 2 {
		return dp(nums)
	}
	dpl, dpr := dp(nums[:len(nums)-1]), dp(nums[1:])
	if dpl > dpr {
		return dpl
	}
	return dpr
}

func Rob33(nums []int) int {
	pre1, pre2, pre3, pre4, n := 0, 0, 0, 0, len(nums)
	if n == 0 {
		return 0
	} else if n == 1 {
		pre2 = nums[0]
	} else if n == 2 {
		pre2, pre4 = nums[0], nums[1]
	} else {
		for i := 0; i < n-1; i++ {
			pre1, pre2 = pre2, pre1+nums[i]
			if pre2 < pre1 {
				pre2 = pre1
			}
		}
		for i := 1; i < n; i++ {
			pre3, pre4 = pre4, pre3+nums[i]
			if pre4 < pre3 {
				pre4 = pre3
			}
		}
	}
	if pre2 > pre4 {
		return pre2
	}
	return pre4
}

// 217
// https://leetcode-cn.com/problems/contains-duplicate/
func ContainsDuplicate(nums []int) bool {
	var stack = make(map[int]bool)
	for _, v := range nums {
		if _, ok := stack[v]; ok {
			return true
		}
		stack[v] = true
	}
	return false
}

// 219
// https://leetcode-cn.com/problems/contains-duplicate-ii/
func ContainsNearbyDuplicate(nums []int, k int) bool {
	var stack = make(map[int]int)
	for kk, v := range nums {
		if _, ok := stack[v]; ok {
			if kk-stack[v] <= k {
				return true
			}
		}
		stack[v] = kk
	}
	return false
}

// 221
// https://leetcode-cn.com/problems/maximal-square/
func MaximalSquare(matrix [][]byte) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}
	min := func(x, y int) int {
		if x > y {
			return y
		}
		return x
	}
	m, n := len(matrix), len(matrix[0])
	dp, side := make([][]int, m+1), 0
	for i := 0; i < m; i++ {
		if i == 0 {
			dp[0] = make([]int, n+1)
		}
		dp[i+1] = make([]int, n+1)
		for j := 0; j < n; j++ {
			dp[i+1][j+1] = 0
			if matrix[i][j] == '1' {
				dp[i+1][j+1] = min(dp[i][j], min(dp[i+1][j], dp[i][j+1])) + 1
			}
			if side < dp[i+1][j+1] {
				side = dp[i+1][j+1]
			}
		}
	}
	return side * side
}

// 222
// https://leetcode-cn.com/problems/count-complete-tree-nodes/
func CountNodes(root *TreeNode) int {
	var num int
	var stack []*TreeNode
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		if stack[0].Left != nil {
			stack = append(stack, stack[0].Left)
		}
		if stack[0].Right != nil {
			stack = append(stack, stack[0].Right)
		}
		stack = stack[1:]
		num++
	}
	return num
}

// 224
// https://leetcode-cn.com/problems/basic-calculator/
func Calculate(s string) int {
	num, carry, stack := 0, 1, []int{0}
	for i := len(s) - 1; i >= 0; i-- {
		switch s[i] {
		case ' ':
			carry = 1
		case '-':
			num, carry, stack[len(stack)-1] = 0, 1, stack[len(stack)-1]-num
		case '+':
			num, carry, stack[len(stack)-1] = 0, 1, stack[len(stack)-1]+num
		case '(':
			num, carry, stack = stack[len(stack)-1]+num, 1, stack[:len(stack)-1]
		case ')':
			num, carry, stack = 0, 1, append(stack, 0)
		default:
			num, carry = num+int(s[i]-48)*carry, carry*10
		}
	}

	return stack[0] + num
}

// 225
// https://leetcode-cn.com/problems/implement-stack-using-queues/
type MyStack struct {
	stack []int
}

func MyStackConstructor() MyStack {
	return MyStack{}
}
func (ms *MyStack) Push(x int) {
	ms.stack = append(ms.stack, x)
}
func (ms *MyStack) Pop() int {
	if ms.Empty() {
		return -1
	}
	var num = ms.stack[len(ms.stack)-1]
	ms.stack = ms.stack[:len(ms.stack)-1]
	return num
}
func (ms *MyStack) Top() int {
	if ms.Empty() {
		return -1
	}
	return ms.stack[len(ms.stack)-1]
}
func (ms *MyStack) Empty() bool {
	return len(ms.stack) == 0
}

// 226
// https://leetcode-cn.com/problems/invert-binary-tree/
func InvertTree(root *TreeNode) *TreeNode {
	if root != nil {
		root.Left, root.Right = root.Right, root.Left
		InvertTree(root.Left)
		InvertTree(root.Right)
	}
	return root
}

// 227
// https://leetcode-cn.com/problems/basic-calculator-ii/
func Calculate2(s string) int {
	numL, numR, res, operate := 0, 0, 0, -1 // 左操作数、右操作数、结果、操作符:1+2-3*4/
	cal := func() int {
		switch operate {
		case 2:
			return numL - numR
		case 3:
			return numL * numR
		case 4:
			return numL / numR
		}
		return numL + numR
	}
	for i := 0; i < len(s); i++ {
		switch s[i] {
		case ' ':
		case '+':
			numL, numR, operate, res = 0, 0, 1, res+cal()
		case '-':
			numL, numR, operate, res = 0, 0, 2, res+cal()
		case '*':
			numL, numR, operate = cal(), 0, 3
		case '/':
			numL, numR, operate = cal(), 0, 4
		default:
			numR = numR*10 + int(s[i]-'0')
		}
	}

	return res + cal()
}

// 228
// https://leetcode-cn.com/problems/summary-ranges/
func SummaryRanges(nums []int) []string {
	var res []string
	var join = func(s, e int) string {
		if s == e {
			return strconv.Itoa(s)
		}
		return strconv.Itoa(s) + `->` + strconv.Itoa(e)
	}
	if len(nums) > 0 {
		start, end := nums[0], nums[0]
		for i := 1; i < len(nums); i++ {
			if nums[i] > nums[i-1]+1 {
				res, start = append(res, join(start, end)), nums[i]
			}
			end = nums[i]
		}
		res = append(res, join(start, end))
	}

	return res
}

// 230
// https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
func KthSmallest(root *TreeNode, k int) int {
	var number, count int
	var find = false
	var order func(root *TreeNode)
	order = func(root *TreeNode) {
		if !find && root != nil {
			order(root.Left)
			count++
			if count == k {
				find = true
				number = root.Val
			}
			order(root.Right)
		}
	}
	order(root)
	return number
}

// 231
// https://leetcode-cn.com/problems/power-of-two/
func IsPowerOfTwo(n int) bool {
	if n < 1 {
		return false
	}
	for n > 1 {
		if n%2 != 0 {
			return false
		}
		n /= 2
	}
	return true
}

// 232
// https://leetcode-cn.com/problems/implement-queue-using-stacks/
type MyQueue struct {
	queue []int
}

func MyQueueConstructor() MyQueue {
	return MyQueue{}
}
func (ms *MyQueue) Push(x int) {
	ms.queue = append(ms.queue, x)
}
func (ms *MyQueue) Pop() int {
	if ms.Empty() {
		return -1
	}
	var num = ms.queue[0]
	ms.queue = ms.queue[1:]
	return num
}
func (ms *MyQueue) Peek() int {
	if ms.Empty() {
		return -1
	}
	return ms.queue[0]
}
func (ms *MyQueue) Empty() bool {
	return len(ms.queue) == 0
}

// 234
// https://leetcode-cn.com/problems/palindrome-linked-list/
func IsPalindrome3(head *ListNode) bool {
	var nums []int
	for head != nil {
		nums = append(nums, head.Val)
		head = head.Next
	}
	for i := 0; i < len(nums)/2; i++ {
		if nums[i] != nums[len(nums)-1-i] {
			return false
		}
	}
	return true
}

// 235
// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
func LowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	if p.Val < root.Val && q.Val < root.Val {
		return LowestCommonAncestor(root.Left, p, q)
	}
	if p.Val > root.Val && q.Val > root.Val {
		return LowestCommonAncestor(root.Right, p, q)
	}
	return root
}

// 236
// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
func LowestCommonAncestor2(root, p, q *TreeNode) *TreeNode {
	var pPath, qPath []*TreeNode
	var findPath func(root *TreeNode, path []*TreeNode)
	findPath = func(root *TreeNode, path []*TreeNode) {
		if root != nil && (len(pPath) == 0 || len(qPath) == 0) {
			path = append(path, root)
			if root.Val == p.Val {
				pPath = append([]*TreeNode{}, path...)
			} else if root.Val == q.Val {
				qPath = append([]*TreeNode{}, path...)
			}
			findPath(root.Left, path)
			findPath(root.Right, path)
		}
	}
	findPath(root, []*TreeNode{})
	for i := len(pPath) - 1; i >= 0; i-- {
		for j := len(qPath) - 1; j >= 0; j-- {
			if pPath[i] == qPath[j] {
				return pPath[i]
			}
		}
	}
	return nil
}

// 237
// https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
func DeleteNode(node *ListNode) {
	node.Val = node.Next.Val
	node.Next = node.Next.Next
}

// 242
// https://leetcode-cn.com/problems/valid-anagram/
func IsAnagram(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}
	var sMap = make(map[rune]int)
	for _, v := range s {
		sMap[v]++
	}
	for _, v := range t {
		if _, ok := sMap[v]; ok {
			sMap[v]--
			if sMap[v] < 0 {
				return false
			}
		} else {
			return false
		}
	}
	return true
}

// 257
// https://leetcode-cn.com/problems/binary-tree-paths/
func BinaryTreePaths(root *TreeNode) []string {
	var findPath func(root *TreeNode, paths []string) []string
	findPath = func(root *TreeNode, paths []string) []string {
		if root == nil {
			return []string{}
		}
		if len(paths) == 0 {
			paths = append(paths, strconv.Itoa(root.Val))
		} else {
			for k, v := range paths {
				paths[k] = v + `->` + strconv.Itoa(root.Val)
			}
		}
		if root.Left == nil && root.Right == nil {
			return paths
		}
		var leftPaths = findPath(root.Left, append([]string{}, paths...))
		var rightPaths = findPath(root.Right, append([]string{}, paths...))
		return append(leftPaths, rightPaths...)
	}
	return findPath(root, []string{})
}

// 258
// https://leetcode-cn.com/problems/add-digits/
func AddDigits(num int) int {
	return 1 + (num-1)%9
}

// 263
// https://leetcode-cn.com/problems/ugly-number/
func IsUgly(n int) bool {
	if n < 1 {
		return false
	}
	for _, v := range []int{2, 3, 5} {
		for n%v == 0 {
			n /= v
		}
	}
	return n == 1
}

// 264
// https://leetcode-cn.com/problems/ugly-number-ii/
func NthUglyNumber(n int) int {
	dp := make([]float64, n+1)
	dp[1] = 1
	p2, p3, p5 := 1, 1, 1
	for i := 2; i <= n; i++ {
		x2, x3, x5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
		dp[i] = math.Min(math.Min(x2, x3), x5)
		if dp[i] == x2 {
			p2++
		}
		if dp[i] == x3 {
			p3++
		}
		if dp[i] == x5 {
			p5++
		}
	}
	return int(dp[n])
}

// 268
// https://leetcode-cn.com/problems/missing-number/
func MissingNumber(nums []int) int {
	var sum = (len(nums) + 1) * len(nums) / 2
	for _, v := range nums {
		sum -= v
	}
	return sum
}

// 278
// https://leetcode-cn.com/problems/first-bad-version/
func FirstBadVersion(n int) int {
	var isBadVersion func(n int) bool
	var left, right = 1, n
	for left < right-1 {
		var middle = (left + right) / 2
		if isBadVersion(middle) {
			right = middle
		} else {
			left = middle
		}
	}
	if isBadVersion(left) {
		right = left
	}
	return right
}

// MoveZeroes
// 283
// https://leetcode-cn.com/problems/move-zeroes/
func MoveZeroes(nums []int) {
	l, r := 0, 0
	for r < len(nums) {
		if nums[r] == 0 {
			r++
		} else {
			if nums[l] == 0 {
				nums[l], nums[r] = nums[r], 0
			}
			l++
			r++
		}
	}
}

// 290
// https://leetcode-cn.com/problems/word-pattern/
func WordPattern(pattern string, str string) bool {
	var strArr = strings.Split(str, ` `)
	if len(pattern) != len(strArr) {
		return false
	}
	var maps1, maps2 = make(map[string]byte), make(map[byte]string)
	for i := 0; i <= len(strArr)-1; i++ {
		if v, ok := maps1[strArr[i]]; ok {
			if v != pattern[i] {
				return false
			}
		} else if v, ok := maps2[pattern[i]]; ok {
			if v != strArr[i] {
				return false
			}
		} else {
			maps1[strArr[i]], maps2[pattern[i]] = pattern[i], strArr[i]
		}
	}
	return true
}

// 292
// https://leetcode-cn.com/problems/nim-game/
func CanWinNim(n int) bool {
	return n%4 != 0
}

// 299
// https://leetcode-cn.com/problems/bulls-and-cows/
func GetHint(secret string, guess string) string {
	var a, b = 0, 0
	var arr = make(map[byte]int)
	var guessArr []byte
	for i := 0; i < len(secret); i++ {
		if secret[i] == guess[i] {
			a++
		} else {
			if _, ok := arr[secret[i]]; !ok {
				arr[secret[i]] = 0
			}
			arr[secret[i]]++
			guessArr = append(guessArr, guess[i])
		}
	}
	for i := 0; i < len(guessArr); i++ {
		if v, ok := arr[guessArr[i]]; ok && v > 0 {
			b++
			arr[guessArr[i]]--
		}
	}
	return fmt.Sprintf(`%dA%dB`, a, b)
}
